package code;

public class Code214 {

	/*
	 * 求最长的回文
	 */
	public int[] calPalindrome(String s){
		StringBuilder sb=new StringBuilder();
		int i,j;
		for(i=0;i<s.length();i++){
			sb.append("#"+s.charAt(i));
		}
		sb.append("#");
		int n=s.length();
		
		int[] p=new int[2*n+1];
		int mx=0;
		int index=0;
		int idx=0;
		for(i=1;i<=2*n;i++){
			if(mx>i)
				p[i]=p[2*index-i]>mx-i?mx-i:p[2*index-i];
			else 
				p[i]=1;
			for(;i-p[i]>=0 && i+p[i]<=2*n && sb.charAt(i-p[i])==sb.charAt(i+p[i]);p[i]++)
				;
			if(i+p[i]>mx){
				mx=i+p[i];
				index=i;
			}
		}
		return p;
	}
	public int min(int a,int b){
		return a>b?b:a;
	}
    public String shortestPalindrome(String s) {
    	int n=s.length();
    	if(n==0)
    		return "";
    	int[] p=calPalindrome(s);
    	int maxLen=0;
    	int i,k=0;
    	for(i=1;i<2*n;i++){
    		if(p[i]==i+1)
    			k=i;
    	}
    	StringBuilder ans=new StringBuilder();
    	int j;
    	k=p[k]-2;
    	for(j=n-1;j>k;j--){
    		ans.append(s.charAt(j));
    	}
    	ans.append(s);
        return ans.toString();
    }
    public static void main(String[] args){
    	String s="abc";
    	System.out.println(new Code214().shortestPalindrome(s));
    }
}
